スケジューリング・ポリシー (scheduling policy)¶

スケジューラ (scheduler) とはカーネルの構成要素で、 次に CPU で実行される実行可能なプロセスを決定するものである。 各々のプロセスには、スケジューリング・ポリシーと 「静的」なスケジューリング優先度 sched_priority が対応付けられ、 これらの設定は sched_setscheduler() で変更できる。 スケジューラは、システム上の全プロセスのスケジューリング・ポリシーと 静的優先度に関する知識に基づいて決定を行う。

通常のスケジューリング・ポリシー (SCHED_OTHER, SCHED_IDLE, SCHED_BATCH) の下でスケジューリングされるプロセスでは、 sched_priority はスケジューリングの決定に使用されない (sched_priority には 0 を指定しなければならない)。

リアルタイム・スケジューリング・ポリシー (SCHED_FIFO, SCHED_RR) の下でスケジューリングされるプロセスは、 sched_priority の値は 1 (最低) から 99 (最高) の範囲となる (数字から分かるように、リアルタイム・プロセスは常に通常のプロセスよりも 高い優先度を持つ)。 ここで注意すべきなのは、POSIX.1-2001 が要求しているのは、 リアルタイム・ポリシーの実装において最低 32 種類の異なる優先度レベルが サポートされることだけであり、いくつかのシステムではこの最低限の数の 優先度しか提供されていない、ということである。 移植性が必要なプログラムでは、 sched_get_priority_min(2) と sched_get_priority_max(2) を使って、あるポリシーがサポートする優先度の範囲を調べるべきである。

概念としては、 スケジューラはその sched_priority の値それぞれに対して 実行可能なプロセスのリストを管理している。 どのプロセスを次に実行するかを決定するために、 スケジューラは静的優先度の最も高い空でないリストを探して、 そのリストの先頭のプロセスを選択する。

各プロセスのスケジューリング・ポリシーは、 そのプロセスが同じ静的優先度を持つプロセスのリストの中のどこに挿入され、 このリストの中をどのように移動するかを決定する。

全てのスケジューリングはプリエンプティブ (preemptive) である: より高い優先度のプロセスが実行可能になると、現在実行中のプロセスは実行権を 取り上げられ (preempted)、そのプロセスの静的優先度レベルの待ちリストに 戻される。スケジューリング・ポリシーは同じ静的優先度を持つ実行可能な プロセスのリストの中で順番のみを決定する。

SCHED_FIFO: ファーストイン・ファーストアウト・スケジューリング¶

SCHED_FIFO は 0 より大きな静的優先度でのみ使用できる。このポリシーでは、 SCHED_FIFO プロセスが実行可能になった場合、 そのポリシーが SCHED_OTHER、 SCHED_BATCH、 SCHED_IDLE の 現在実行中のプロセスは直ちに実行権を取り上げられる。 SCHED_FIFO は時分割のない単純なスケジューリング・アルゴリズムである。 SCHED_FIFO ポリシーでスケジューリングされているプロセスには以下の ルールが適用される:

• より高い優先度の他のプロセスによって取って代わられた SCHED_FIFO プロセスはその優先度のリストの先頭に留まり続け、 より高い優先度のプロセス全てが停止 (block) した場合に実行を再開する。
• SCHED_FIFO プロセスが実行可能になった時、その優先度のリストの最後 に挿入される。
• sched_setscheduler() や sched_setparam(2) は pid で指定された SCHED_FIFO (または SCHED_RR) プロセスが 実行可能な場合、リストの最初に置く。 結果として、もし優先度が同じだった場合、 現在実行中のプロセスに先んじるかもしれない。 (POSIX.1-2001 ではプロセスはリストの最後に行くべきと規定されている。)
• sched_yield(2) を呼び出したプロセスはリストの最後に置かれる。

その他のイベントによって SCHED_FIFO ポリシーで スケジューリングされるプロセスが同じ優先度の実行可能な プロセスの待ちリストの中を移動することはない。

SCHED_FIFO プロセスは I/O 要求によって停止するか、 より高い優先度のプロセスによって置きかえられるか、 sched_yield(2) を呼び出すまで実行を続ける。

SCHED_RR: ラウンド・ロビン (round robin) ・スケジューリング¶

SCHED_RR は SCHED_FIFO の単純な拡張である。 上述された SCHED_FIFO に関する記述は全て SCHED_RR に 適用できる。異なるのはそれぞれのプロセスは最大時間単位までしか実行できない ということである。SCHED_RR プロセスが時間単位と同じかそれより 長い時間実行されると、その優先度のリストの最後に置かれる。 より高い優先度のプロセスによって置きかえられ、その後実行を再開した SCHED_RR プロセスは、そのラウンド・ロビン時間単位を完全に使い切る まで実行される。その時間単位の長さは sched_rr_get_interval(2) を使って取得できる。

SCHED_OTHER: Linux のデフォルトの時分割スケジューリング¶

SCHED_OTHER は静的優先度 0 でのみ使用できる。 SCHED_OTHER は Linux 標準の時分割スケジューラで、 特別なリアルタイム機構を必要としていない全てのプロセスで使用される。 実行するプロセスは、静的優先度 0 のリストから、このリストの中だけで 決定される「動的な」優先度 (dynamic priority) に基いて決定される。 動的な優先度は (nice(2) や setpriority(2) により設定される) nice 値に基づいて決定されるもので、 単位時間毎に、プロセスが実行可能だが、スケジューラにより実行が拒否された 場合にインクリメントされる。 これにより、全ての SCHED_OTHER プロセスでの公平性が保証される。

SCHED_BATCH: バッチプロセスのスケジューリング¶

(Linux 2.6.16 以降) SCHED_BATCH は静的優先度 0 でのみ使用できる。 このポリシーは (nice 値に基づく) 動的な優先度にしたがってプロセスの スケジューリングが行われるという点で、SCHED_OTHER に似ている。 異なるのは、このポリシーでは、プロセスが常に CPU に負荷のかかる (CPU-intensive) 処理を行うと、スケジューラが仮定する点である。 スケジューラはプロセスを呼び起こす毎にそのプロセスにスケジューリング上の ペナルティを少し課し、その結果、このプロセスはスケジューリングの決定で 若干冷遇されるようになる。

このポリシーは、非対話的な処理だがその nice 値を下げたくない処理や、 (処理のタスク間で) 余計なタスクの置き換えの原因とある対話的な処理なしで 確定的な (deterministic) スケジューリング・ポリシーを適用したい処理に 対して有効である。

SCHED_IDLE: 非常に優先度の低いジョブのスケジューリング¶

(Linux 2.6.23 以降) SCHED_IDLE は静的優先度 0 でのみ使用できる。 このポリシーではプロセスの nice 値はスケジューリングに影響を与えない。

非常に低い優先度でのジョブの実行を目的としたものである (非常に低い優先度とは、ポリシー SCHED_OTHER か SCHED_BATCH での nice 値 +19 よりさらに低い優先度である)。

特権とリソース制限¶

2.6.12 より前のバージョンの Linux カーネルでは、 特権プロセス (CAP_SYS_NICE ケーパビリティを持つプロセス) だけが 0 以外の静的優先度を設定する (すなわち、リアルタイム・スケジューリング・ポリシーを設定する) ことができる。 非特権プロセスができる変更は SCHED_OTHER ポリシーを設定することだけであり、さらにこの変更を行えるのは sched_setscheduler() の呼び出し元の実効ユーザ ID がポリシーの変更対象プロセス (pid で指定されたプロセス) の実ユーザ ID か実効ユーザ ID と 一致する場合だけである。

Linux 2.6.12 以降では、リソース制限 RLIMIT_RTPRIO が定義されており、 スケジューリング・ポリシーが SCHED_RR と SCHED_FIFO の場合の、非特権プロセスの静的優先度の上限を定めている。 スケジューリング・ポリシーと優先度を変更する際のルールは以下の通りである。

• 非特権プロセスに 0 以外の RLIMIT_RTPRIO ソフト・リミットが設定されている場合、 非特権プロセスはそのプロセスのスケジューリング・ポリシーと優先度を 変更できるが、優先度を現在の自身の優先度と RLIMIT_RTPRIO ソフト・リミットの大きい方よりも高い値に設定できないという制限が課される。
• RLIMIT_RTPRIO ソフト・リミットが 0 の場合、優先度を下げるか、 リアルタイムでないポリシーへ切り替えるかの変更だけが許可される。
• ある非特権プロセスが別のプロセスに対してこれらの変更を行う際にも、 同じルールが適用される。変更を行えるのは、変更を行おうとするプロセス の実効ユーザ ID が変更対象のプロセスの実ユーザ ID か実効ユーザ ID と 一致している場合に限られる。
• SCHED_IDLE には特別なルールが適用され、 このポリシーの下で動作する非特権プロセスは、リソース制限 RLIMIT_RTPRIO の値にかかわらず自身のポリシーを変更することができない。

特権プロセス (CAP_SYS_NICE ケーパビリティを持つプロセス) の場合、 RLIMIT_RTPRIO の制限は無視される; 古いカーネルと同じように、スケジューリング・ポリシーと優先度に対し 任意の変更を行うことができる。 RLIMIT_RTPRIO に関するもっと詳しい情報は getrlimit(2) を参照のこと。

応答時間 (response time)¶

I/O 待ちで停止したより高い優先度のプロセスは再びスケジューリングされる 前にいくらかの応答時間がかかる。デバイス・ドライバーを書く場合には "slow interrupt" 割り込みハンドラーを使用することで この応答時間を劇的に減少させることができる。

その他¶

子プロセスは fork(2) の際に親プロセスのスケジューリング・ポリシーとパラメータを継承する。 execve(2) の前後で、スケジューリング・ポリシーとパラメータは保持される。

リアルタイム・プロセスは大抵、ページングの待ち時間を避けるために mlock(2) や mlockall(2) を使ってメモリ・ロックをしなければならない。

SCHED_FIFO や SCHED_RR でスケジューリングされる プロセスが停止せずに無限ループに陥ると、 他の全てのより低い優先度のプロセスを永久に停止 (block) させてしまうので、 ソフトウェア開発者はコンソールのシェルの静的優先度をテストする アプリケーションよりも常に高く保つべきである。 これによって期待通りに停止したり終了したりしないリアルタイム・ アプリケーションを緊急終了させることが可能になる。 getrlimit(2) のリソース制限 RLIMIT_RTTIME の説明も参照のこと。

POSIX システムでは <unistd.h> に _POSIX_PRIORITY_SCHEDULING が定義されている場合にのみ sched_setscheduler() と sched_getscheduler() が使用できる。

本流の Linux カーネルでのリアルタイム機能¶

カーネル 2.6.18 から現在まで、 Linux は徐々にリアルタイム機能を備えつつあるが、 これらの機能のほとんどは、 Ingo Molnar, Thomas Gleixner, Steven Rostedt らによって開発された、 以前の realtime-preempt パッチからのものである。 これらのパッチが本流のカーネルに完全にマージされるまでは (マージの完了はカーネル 2.6.30 あたりの予定)、 最高のリアルタイム性能を達成するには realtime-preempt パッチを 組み込まなければならない。 これらのパッチは

patch-kernelversion-rtpatchversion

という名前で、 http://www.kernel.org/pub/linux/kernel/projects/rt/ からダウンロードできる。

このパッチが適用されず、かつパッチの内容の本流のカーネルへのマージが 完了するまでは、カーネルの設定では CONFIG_PREEMPT_NONE, CONFIG_PREEMPT_VOLUNTARY, CONFIG_PREEMPT_DESKTOP の 3つのプリエンプション・クラス (preemption class) だけが提供される。 これらのクラスでは、最悪の場合のスケジューリング遅延がそれぞれ 全く減らない、いくらか減る、かなり減る。

パッチが適用された場合、またはパッチの内容の本流のカーネルへのマージが 完了した後では、上記に加えて設定項目として CONFIG_PREEMPT_RT が利用可能になる。この項目を選択すると、 Linux は通常のリアルタイム・オペレーティングシステムに変身する。 この場合には、 sched_setscheduler() で選択できる FIFO と RR のスケジューリング・ポリシーは、 真のリアルタイム優先度を持つプロセスを最悪の場合のスケジューリング遅延が 最小となる環境で動作させるために使われることになる。